// 给你一个整数数组 nums 和一个整数 target 。

// 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

// 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
// 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。


// 输入：nums = [1,1,1,1,1], target = 3
// 输出：5
// 解释：一共有 5 种方法让最终目标和为 3 。
// -1 + 1 + 1 + 1 + 1 = 3
// +1 - 1 + 1 + 1 + 1 = 3
// +1 + 1 - 1 + 1 + 1 = 3
// +1 + 1 + 1 - 1 + 1 = 3
// +1 + 1 + 1 + 1 - 1 = 3

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/target-sum
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

// 看了题解，动态规划
// 加法-减法=target
// 加法+减法=总和
// 2*加法=target+总和 /2
// 01背包
// 背包为target，nums为物品，dp[i]：i为target，dp[i]为当前i装满的可能性

// 执行用时：
// 8 ms
// , 在所有 C++ 提交中击败了
// 90.33%
// 的用户
// 内存消耗：
// 9 MB
// , 在所有 C++ 提交中击败了
// 50.05%
// 的用户


class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        int res=0;
        for(int i=0;i<nums.size();i++){
            sum = sum+nums[i];
        }
        // 注意这种情况
        if(target>sum){
            return res;
        }
        int flag = (sum+target)%2;
        if(flag==1){
            return res;
        }
        
        int w = (sum+target)/2;
        vector<int> dp(w+1,0);
        // 0时补妆，存在一种
        dp[0] = 1;
        for(int i=0;i<nums.size();i++){
            for(int j=w;j>=nums[i];j--){
                dp[j] = dp[j]+dp[j-nums[i]];
            }
        }
        return dp[w];
    }
};
